#include "BTreeNode.h"
#include <stdio.h>
#include <string.h>

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  MAX_MEMORY = 85; // 85 is the max number of nodes possible from 1024
                   //buffer
  RC rc = pf.read (pid, buffer);
  if (rc == RC_INVALID_PID)
  {
    return RC_INVALID_PID;
  }
  int current_bytes = (int) buffer[0];
  int buffer_on = 4;
  int memory_on = 0;
  int node_on = 0;
  while (buffer_on != PageFile::PAGE_SIZE - 4 && current_bytes != -1)
  {
    if (node_on == 0)
      memory[memory_on].rid.pid = current_bytes;
    else if (node_on == 1)
      memory[memory_on].rid.sid = current_bytes;
    else if (node_on == 2)
      memory[memory_on].key = current_bytes;
    node_on++;
    if (node_on == 3)
    {
      node_on = 0;
      memory_on++;
    }
    current_bytes = (int) buffer[buffer_on];
    buffer_on += 4;
  }
  key_count = memory_on;
  for (int i = key_count + 1; i < MAX_MEMORY; i++)
  {
    memory[i].key = -1;
  }
  next_leaf = (int) buffer[PageFile::PAGE_SIZE - 4];
  return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
  memcpy (buffer, memory, PageFile::PAGE_SIZE - 4);
  memcpy (&(buffer[PageFile::PAGE_SIZE - 4]), &next_leaf, 4);
  RC rc = pf.write (pid, buffer);
  if (rc == RC_INVALID_PID)
    return RC_INVALID_PID;
  if (rc == RC_FILE_WRITE_FAILED)
    return RC_FILE_WRITE_FAILED;
  return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  return key_count;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  if (key_count == MAX_MEMORY)
    return RC_NODE_FULL;

  if (key_count == 0)
  {
    memory[0].key = key;
    memory[0].rid = rid;
    key_count++;
    return 0;
  }

  for (int i = 0; i < key_count; i++)
  {
    if (memory[i].key > key)
    {
      for (int j = key_count; j > i; j--)
      {
        memory[j] = memory[j-1];
      }
      memory[i].key = key;
      memory[i].rid = rid;
      key_count++;
      break;
    }
  }
  return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
  // assume our leafnode is full when this function is called

  int current = 0;
  for (int i = MAX_MEMORY / 2 + 1; i < MAX_MEMORY; i++)
  {
    sibling.memory[current] = memory[i];
    current++;
    memory[i].key = -1;
  }
  key_count = MAX_MEMORY / 2 + 1;
  sibling.key_count = MAX_MEMORY / 2;
  if (key > memory[MAX_MEMORY / 2].key)
    sibling.insert (key, rid);
  else
  {
    insert (key, rid);
    sibling.insert(memory[MAX_MEMORY / 2 + 1].key, 
                   memory[MAX_MEMORY / 2 + 1].rid);
    memory[MAX_MEMORY / 2 + 1].key = -1;
    key_count--;
  }
  siblingKey = sibling.memory[0].key;
  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  if (searchKey < memory[0].key)
    return RC_INVALID_CURSOR;
  for (int i = 0; i < key_count; i++)
  {
    if (memory[i].key >= searchKey)
    {
      eid = i;
      return 0;
    }
  }
  return RC_INVALID_CURSOR; // i dont know if this is the right error
                            // but it means searchKey is > all keys
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
  if (eid < 0 || eid >= key_count)
    return RC_INVALID_CURSOR; // i dont know if this right either
  key = memory[eid].key;
  rid = memory[eid].rid;
  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
  return next_leaf;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  if (pid < 0) // i cant check upper bound, only page file can do that
    return RC_INVALID_PID;
  next_leaf = pid;
  return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	pf.read(pid, buffer);
	
	int ncount = 0;
	
	for(int i = 0; i < 127; i++)
	{
		if((int)buffer[i*8+4] == -1)
		{
			break; //empty key
		}
		
		nonleafnodes[ncount].before = (int)buffer[i*8];
		nonleafnodes[ncount].key = (int)buffer[i*8+4];
		nonleafnodes[ncount].after = (int)buffer[(i+1)*8];
		ncount++;
	}
	
	key_count = ncount;
	
	//signal end of occupied keys
	if(ncount != 127)
		nonleafnodes[ncount].key = -1;
	
	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{	
	int i = 0;
	//if key is zero then stop
	for(i = 0; i < 127; i++)
	{
		if(nonleafnodes[i].key == -1)
		{
			memcpy(&buffer[i*8+4], &nonleafnodes[i].key, sizeof(int));
			break; //end early
		}
		memcpy(&buffer[i*8], &nonleafnodes[i].before, sizeof(int));
		memcpy(&buffer[i*8+4], &nonleafnodes[i].key, sizeof(int));
		memcpy(&buffer[(i+1)*8], &nonleafnodes[i].after, sizeof(int));
	} //infinity pointer automatically taken care of
	
	pf.write(pid, buffer);
	return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	return key_count;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	//check if node is full
	if(getKeyCount() == 127)
		return RC_NODE_FULL;
		
	int i = 0, j = 0;
	
	if(getKeyCount() == 0) //empty case
	{
		nonleafnodes[0].before = pid;
		nonleafnodes[0].key = key;
		nonleafnodes[0].after = -1;
		key_count++;
		return 0;
	}
	
	if(key < nonleafnodes[0].key) //less than first element
	{
		//shift them all to the right, start from the end
		for(i = getKeyCount(); i > 0; i--)
		{
			nonleafnodes[i].before = nonleafnodes[i-1].before;
			nonleafnodes[i].key = nonleafnodes[i-1].key;
			nonleafnodes[i].after = nonleafnodes[i-1].after;
		}
		
		//set the new end
		nonleafnodes[getKeyCount()+1].key = -1;
		
		//perform the insertion
		nonleafnodes[0].before = pid;
		nonleafnodes[0].key = key;
		nonleafnodes[0].after = nonleafnodes[i+2].before;
		key_count++;
		return 0;
	}
	
	for(i = 0; i < getKeyCount(); i++) //general case
	{
		if(key > nonleafnodes[i].key)
		{
			//shift them all to the right, start from the end
			for(j = getKeyCount(); j > i; j--)
			{
				nonleafnodes[j].before = nonleafnodes[j-1].before;
				nonleafnodes[j].key = nonleafnodes[j-1].key;
				nonleafnodes[j].after = nonleafnodes[j-1].after;
			}
			
			//set the new end
			nonleafnodes[getKeyCount()].key = -1;
			
			//perform the insertion
			nonleafnodes[i+1].before = pid;
			nonleafnodes[i+1].key = key;
			nonleafnodes[i+1].after = nonleafnodes[i+2].before;
			key_count++;
			return 0;
		}
	}
	return -1;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int count = 0;
	int newpos = 0;
	int i, j = 0;
	
	if(key < nonleafnodes[0].key)
	{
		goto flag; //lol
	}
	
	for(i = 0; i < 127; i++)
	{
		if(key > nonleafnodes[i].key)
		{
			if(i < 127/2) //insertion takes place in original node
			{
flag:
				//copy to new node
				for(j = 127 / 2; j < 127; j++)
				{
					sibling.nonleafnodes[count].before = nonleafnodes[j].before;
					sibling.nonleafnodes[count].key = nonleafnodes[j].key;
					sibling.nonleafnodes[count].after = nonleafnodes[j].after;
					nonleafnodes[j].before = -1;
					nonleafnodes[j].key = -1;
					nonleafnodes[j].after = -1;
					key_count--;
					count++;
				}
				
				//insert in first half
				//shift them all to the right, start from the end
				for(j = getKeyCount(); j > i; j--)
				{
					nonleafnodes[j].before = nonleafnodes[j-1].before;
					nonleafnodes[j].key = nonleafnodes[j-1].key;
					nonleafnodes[j].after = nonleafnodes[j-1].after;
				}
				
				nonleafnodes[i+1].before = pid;
				nonleafnodes[i+1].key = key;
				
				//infinity node case
				/* do all pointers have to point to unique nodes?*/
				if(nonleafnodes[i+2].key == -1)
				{ //next key is in the new block
					nonleafnodes[i+1].key = sibling.nonleafnodes[0].before;
				}
				else
				{
					nonleafnodes[i+1].after = nonleafnodes[i+2].before;
				}
				break;
			}
			else //we need to insert into new node
			{
				for(j = 127 / 2 + 1; j != i+1; j++)
				{
					sibling.nonleafnodes[count].before = nonleafnodes[j].before;
					sibling.nonleafnodes[count].key = nonleafnodes[j].key;
					sibling.nonleafnodes[count].after = nonleafnodes[j].after;
					nonleafnodes[j].before = -1;
					nonleafnodes[j].key = -1;
					nonleafnodes[j].after = -1;
					key_count--;
					count++;
				}
				
				//insert key
				sibling.nonleafnodes[count].before = pid;
				sibling.nonleafnodes[count].key = key;
				sibling.nonleafnodes[count].after = nonleafnodes[j+1].before;
				count++;
				
				for(j = i + 2; j < 127; j++)
				{
					sibling.nonleafnodes[count].before = nonleafnodes[j].before;
					sibling.nonleafnodes[count].key = nonleafnodes[j].key;
					sibling.nonleafnodes[count].after = nonleafnodes[j].after;
					nonleafnodes[j].before = -1;
					nonleafnodes[j].key = -1;
					nonleafnodes[j].after = -1;
					key_count--;
					count++;
				}
			}
			break;
		}
	}
	
	midKey = nonleafnodes[127/2].key;
	
	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	for(int i = 0; i < 127; i++)
	{
		if(nonleafnodes[i].key == searchKey)
		{
			pid = nonleafnodes[i].before;
			return 0;
		}
	}
	return RC_INVALID_PID; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	nonleafnodes[0].before = pid1;
	nonleafnodes[0].key = key;
	nonleafnodes[0].after = pid2;
	return 0;
}
